#ifndef _DYNAMICVORONOI_H_
#define _DYNAMICVORONOI_H_

#include <queue>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "bucketedqueue.h"


class DynamicVoronoi {
public:
  DynamicVoronoi();
  ~DynamicVoronoi();

  void initializeEmpty(int _sizeX, int _sizeY, bool initGridMap=true);
  void initializeMap(int _sizeX, int _sizeY, bool** _gridMap);

  void occupyCell(int x, int y);
  void clearCell(int x, int y);
  void exchangeObstacles(std::vector<INTPOINT>& newObstacles);

  void update(bool updateRealDist=true);
  void prune();
  void updateAlternativePrunedDiagram();
  int** alternativePrunedDiagram(){
    return alternativeDiagram;
  };

  int getNumVoronoiNeighborsAlternative(int x, int y);
  bool isVoronoiAlternative( int x, int y );
  
  float getDistance( int x, int y );
  bool isVoronoi( int x, int y );
  bool isOccupied(int x, int y);
  std::vector<std::pair<int, int>> visualize(const char *filename = "result.ppm");

  unsigned int getSizeX() {return sizeX;}
  unsigned int getSizeY() {return sizeY;}

private:  
  struct dataCell {
    float dist;
    char voronoi;     // 描述栅格状态的值
    char queueing;    // 标记栅格的处理情况
    int obstX;        // 每个符合条件的cell只有一处根即为障碍物点
    int obstY;
    bool needsRaise;  // 是否需要去除障碍物属性(更新)
    int sqdist;       // 非障碍物点到障碍物点的完全平方距离
  };

  typedef enum{
    voronoiKeep = -4,   // 通过修剪得到的voronoi顶点
    freeQueued = -3,    // 标记为要修剪的点，表示已经在集合sortedPruneQueue内
    voronoiRetry = -2,  // 该栅格点需要重新筛选
    voronoiPrune = -1,  // 该栅格点已经进行了修剪
    free = 0,           // voronoi顶点
    occupied = 1        // 栅格为障碍物 (实际操作中这个属性既可以修饰障碍物也可以修饰自由区域)
  } State;

  typedef enum{
    fwNotQueued = 1,  // 初始状态
    fwQueued = 2,     // 开集中
    fwProcessed = 3,  // 已处理状态
    bwQueued = 4,     // 需要移除的障碍物点
    bwProcessed = 1   // 已经移除了该障碍物
  } QueueingState;

  typedef enum{
    invalidObstData = SHRT_MAX / 2
  } ObstDataState; // 短整型（short）最大值（SHRT_MAX）除以2

  typedef enum{
    pruned,   // 修剪
    keep,     // 保留
    retry     // 重试
  } markerMatchResult;

  // methods
  void setObstacle(int x, int y);
  void removeObstacle(int x, int y);
  inline void checkVoro(int x, int y, int nx, int ny, dataCell& c, dataCell& nc);

  void recheckVoro();
  void commitAndColorize(bool updateRealDist=true);
  inline void reviveVoroNeighbors(int &x, int &y);

  inline bool isOccupied(int &x, int &y, dataCell &c);
  inline markerMatchResult markerMatch(int x, int y);
  inline bool markerMatchAlternative(int x, int y);

  // queues
  BucketPrioQueue<INTPOINT> mOpen;            // 开集合

  std::queue<INTPOINT> pruneQueue;            // 修剪的队列
  BucketPrioQueue<INTPOINT> sortedPruneQueue; // 修剪集合

  std::vector<INTPOINT> removeList;           // 记录去除障碍物属性的集合
  std::vector<INTPOINT> addList;              // 本身是障碍物并且周围一圈存在自由区域的集合
  std::vector<INTPOINT> lastObstacles;        // 配合removeList使用

  // maps
  int sizeY;              // 记录地图的高
  int sizeX;              // 记录地图的宽
  dataCell** mData;       // 描述地图中每个栅格的状态
  bool** gridMap;         // 记录传入的地图数据

  bool allocatedGridMap;  // 
  int** alternativeDiagram;

  double sqrt2;
};


#endif







